package summer.graph;

import java.util.*;

public class Solution1129 {
    public int[] shortestAlternatingPaths1(int n, int[][] redEdges, int[][] blueEdges) {
        List<List<Integer>> redList = new LinkedList<>();
        List<List<Integer>> blueList = new LinkedList<>();
        for (int i = 0; i < n; i++) {
            redList.add(new LinkedList<>());
            blueList.add(new LinkedList<>());
        }
        for (int[] curEdge : redEdges) {
            redList.get(curEdge[0]).add(curEdge[1]);
        }
        for (int[] curEdge : blueEdges) {
            blueList.get(curEdge[0]).add(curEdge[1]);
        }
        int dis = 0;
        int[] redRes = new int[n];
        int[] blueRes = new int[n];
        Arrays.fill(redRes, Integer.MAX_VALUE);
        Arrays.fill(blueRes, Integer.MAX_VALUE);
        redRes[0] = 0;
        blueRes[0] = 0;
        LinkedList<int[]> queue = new LinkedList<>();
        queue.add(new int[]{0, 0});
        queue.add(new int[]{0, 1});
        while (!queue.isEmpty()) {
            dis++;
            int curSize = queue.size();
            while (curSize-- > 0) {
                int[] curs = queue.removeFirst();
                if (curs[1] == 0) {
                    List<Integer> list = redList.get(curs[0]);
                    for (int x : list) {
                        if (dis < redRes[x]) {
                            redRes[x] = dis;
                            queue.add(new int[]{x, 1});
                        }
                    }
                } else {
                    List<Integer> list = blueList.get(curs[0]);
                    for (int x : list) {
                        if (dis < blueRes[x]) {
                            blueRes[x] = dis;
                            queue.add(new int[]{x, 0});
                        }
                    }
                }
            }
        }
        int[] res = new int[n];
        for (int i = 0; i < n; i++) {
            res[i] = Math.min(redRes[i], blueRes[i]);
            if (res[i] == Integer.MAX_VALUE) res[i] = -1;
        }
        return res;
    }

    public int[] shortestAlternatingPaths(int n, int[][] redEdges, int[][] blueEdges) {
        List<List<Integer>> redEdge = new ArrayList<>();
        List<List<Integer>> blueEdge = new ArrayList<>();
        for (int i = 0; i < n; i++) {
            redEdge.add(new ArrayList<>());
            blueEdge.add(new ArrayList<>());
        }
        for (int[] edge : redEdges) {
            redEdge.get(edge[0]).add(edge[1]);
        }
        for (int[] edge : blueEdges) {
            blueEdge.get(edge[0]).add(edge[1]);
        }
        int dis = 0;
        int[] redRes = new int[n];
        int[] blueRes = new int[n];
        Arrays.fill(redRes, Integer.MAX_VALUE);
        Arrays.fill(blueRes, Integer.MAX_VALUE);
        redRes[0] = 0;
        blueRes[0] = 0;
        LinkedList<int[]> queue = new LinkedList<>();
        queue.add(new int[]{0, 0});
        queue.add(new int[]{0, 1});
        while (!queue.isEmpty()) {
            dis++;
            int size = queue.size();
            while (size-- > 0) {
                int[] x = queue.removeFirst();
                if (x[1] == 1) {
                    List<Integer> list = redEdge.get(x[0]);
                    for (int cur : list) {
                        if (dis < redRes[cur]) {
                            redRes[cur] = dis;
                            queue.add(new int[]{cur, 0});
                        }
                    }
                } else {
                    List<Integer> list = blueEdge.get(x[0]);
                    for (int cur : list) {
                        if (dis < blueRes[cur]) {
                            blueRes[cur] = dis;
                            queue.add(new int[]{cur, 1});
                        }
                    }
                }
            }
        }
        int[] res = new int[n];
        for (int i = 0; i < n; i++) {
            res[i] = Math.min(redRes[i], blueRes[i]);
        }
        return res;
    }
}
